package com.ljx.DaJieJieShe;

import com.ljx.Dynamic.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 李加喜
 * @Package com.ljx.DaJieJieShe
 * @date 2021-11-13 10:23
 */
public class TreeDaJiaJieShe {
    public static void main(String[] args) {
        Map<TreeNode, Integer> map = new HashMap<>();
    }

    public int rob(TreeNode root, Map<TreeNode, Integer> map) {
        if (root == null) {
            return 0;
        }
        if (map.containsKey(root)) {
            return map.get(root);
        }
        // 当前强 并且强下一家
        int go = root.val + (root.left == null ? 0 : rob(root.left.left, map) + rob(root.left.right, map))
                + (root.right == null ? 0 : rob(root.right.left, map) + rob(root.right.right, map));
        // 当前不强
        int out = rob(root.right, map) + rob(root.left, map);
        int res = Math.max(go, out);
        map.put(root, res);
        return res;
    }

    public int rob1(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }

    /**
     * 返回一个大小为 2 的数组 arr
     * arr[0] 表示不抢 root 的话，得到的最大钱数
     * arr[1] 表示抢 root 的话，得到的最大钱数
     */
    private int[] dp(TreeNode root) {
        if (root == null) {
            return new int[]{0,0};
        }
        int[] left=dp(root.left);
        int[] right=dp(root.right);
        // 当前强
        int rob=root.val+left[0]+right[0];
        // 当前不强  下一家前不强看大小
        int out=Math.max(left[1],left[0])+Math.max(right[0],right[1]);
        return new int[]{rob,out};
    }

}
